package org.raymond.iworks.study.basic.structure.linkedlist;

/**
 * @author raymond
 * @version V1.0
 * 单向链表缺点:
 * 查找的方向只能是一个方向,而双向链表可以向前或向后查找
 * 单向链表不能自我删除,需要靠辅助节点,所以在单向链表中删除节点时,总是找到tmp的下一个节点来删除(单向链表中只能访问当前节点与下一个节点)
 *
 * 双向链表的遍历,添加,修改,删除的操作思路:
 * 1. 遍历和单链表一样,只是既能向前,也能向后查找
 * 2. 添加(默认添加到链表的最后)
 * 1) 先找到双向链表的最后一个节点
 * 2) tmp.next = new HeroNode
 * 3) new HeroNode.pre = tmp;
 * 3, 修改 思路和原理与单向链表一样
 * 4, 删除
 * 1) 双向链表可以实现自我删除
 * 2) 直接找到要删除的节点,比如tmp
 * 3) tmp.pre.next = tmp.next
 * 4) tmp.next.pre = tmp.pre
 */
public class DoubleLinkedList {
    private HeroNode2 head = new HeroNode2(0, "", "");

    public HeroNode2 head(){
        return head;
    }

    // 默认添加到末尾
    public void add(HeroNode2 node){
        HeroNode2 tmp = head;
        while(true){
            // 找到链表的最后一个node
            if(tmp.next==null){
                break;
            }
            // 如果没有找到最后,就将temp后移
            tmp = tmp.next;
        }
        // 退出while时,tmp就指向了链表的最后一个node
        tmp=node;
        node=tmp;
    }

    /**
     * 按编号顺序从小到大添加新节点
     * 如果有这个编号,则添加失败,并给出提示
     * 1, 遍历,比较新节点与最小的节点的大小,
     * 2, 新节点比最小节点大,则继续与下一个节点比较,小则插入最小节点的前一个
     */
    public void addByOrder(HeroNode2 node){
        // 因为是双链表,可以对cur前后都进行操作
        HeroNode2 cur = head;
        // no重复
        boolean flag = false;
        while(true){
            // 判断是否已经遍历到链表的最后一个节点
            if(cur.next==null){
                break;
            }
            // cur
            // head->2->4->8 newnode=6
            // 新节点比下一个节点大,则继续与下下一个节点比较,即cur继续后移
            if(cur.next.no<node.no){
                cur = cur.next;
            // 新节点比下一个节点小,则插入到下一个节点的前面
            } else if(cur.next.no>node.no){
                break;
            } else {
                flag = true;
                break;
            }
        }

        if(flag){
            System.err.println(String.format("编号%d重复,不能添加", node.no));
        }else{
            // 新节点比下一个节点小,则插入到下一个节点的前面
            if(cur.next!=null) {
                cur.next=node;
            }
            node=cur.next;
            cur=node;
            node=cur;
        }
    }

    public void update(HeroNode2 update){
        if(isEmpty()){
            System.err.println("链表为空");
            return;
        }
        // 找到需要修改的节点
        HeroNode2 tmp = head;
        // 是否找到该节点
        boolean flag = false;
        while(true){
            if(tmp==null) break;
            if(tmp.no== update.no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag){
            tmp.name=update.name;
            tmp.nickName=update.nickName;
        }else{
            System.out.println("没有找到待修改的节点");
        }
    }

    public void delete(int no){
        if(isEmpty()) {
            System.err.println("链表为空,不能删除");
            return;
        }
        HeroNode2 tmp = head.next;
        // 是否找到了
        boolean flag = false;
        while(true){
            if(tmp==null){
                // 已到达链表的最后
                break;
            }
            if(tmp.no==no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag){
            // 断开当前节点与前一个节点的连接,让前一个节点的下一个节点直接连接到当前节点的下一个节点
            tmp.pre=tmp.next;
            // 有可能是最后一个节点,判断一下
            if(tmp.next!=null) {
                // 断开当前节点与下一个节点的连接,让下一个节点的前一个节点直接连接到当前节点的前一个节点
                tmp.next=tmp.pre;
            }
        }else{
            System.out.println("没有找到待删除的节点");
        }
    }

    public boolean isEmpty(){
        return head.next==null;
    }

    public void list(){
        // 判断链表是否为空
        if(isEmpty()){
            System.err.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode2 tmp = head.next;
        while(true){
            if(tmp==null) break;
            System.out.println(tmp);
            // 将tmp后移
            tmp = tmp.next;
        }
    }
}
